Current scheduling methods used for allocating limited network resources such as network bandwidth include GPS related scheduling algorithms and Round-Robin related scheduling algorithms. Round-Robin related scheduling algorithms typically allocate bandwidth on a rotating basis. When there is great variance in the sizes of data packets, Round-Robin related scheduling algorithms have been found to allocate bandwidth unfairly. GPS related scheduling algorithms include Weighted Fair Queuing (WFQ), Worst-Case Fair Weighted Fair Queuing (WF2Q), and Self Clocked Fair Queuing (SCFQ). GPS related scheduling algorithms compute a virtual start and finish time to each packet and schedule packets having virtual finish times that are smallest.
In order to identify the packet with the smallest virtual finish time, GPS related schedulers typically utilize a sorter. For practical applications today such as a 10 Gbps network node with 128 inputs, the sorter needs to make a scheduling decision 20 million times a second. Thus, the sorter needs to identify a smallest virtual finish time among 128 numbers in 50 ns.
Traditional software solutions used for performing sorting were found to be effective only in low throughput situations. Traditional hardware approaches typically involved building a parallel comparing tree. These hardware solutions required a large number of resources and limited the GPS related scheduler to a few number of queues.